package review;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


public class LeetCode_day6_review {
	
	/**
	 * To reverse pre->1->2->3->...; k = 3; ind = node(1);
	 * 
	 * node(2).next = node(1); pre->1<-2 3->...
	 * node(3).next = node(2); pre->1<-2<-3->...
	 * node(1).next = after;
	 * pre.next = node(3)
	 * newPre = node(3)
	 * 
	 * @param head
	 * @param k
	 * @return
	 */
	public static ListNode reverseNodesInKGroup(ListNode head, int k){
		//check input valid
		if(head == null) return null;
		int length = 1;
		ListNode temp = head;
		while(temp.next != null) {
			temp = temp.next;
			length++;
		}
		temp = temp.next;
		if(length < k) return head;//no need to reverse
		
		//find the new head;
		ListNode newHead = head;
		for(int i = 1 ; i < k ; i++){
			newHead = newHead.next;
		}
		ListNode ind = head;//array pointer to indicate the current position of execution
		ListNode pre = null, after = null;
		
		while(length >= k){
			ListNode newPre = ind;
			ListNode middle = ind.next;
			
			for(int i = 1 ; i < k ; i++){
				middle.next = ind;
				ind = middle;
				middle = middle.next;
				length--;
			}
			if(pre != null) pre.next = ind;
			newPre.next = middle;
			pre = newPre;
			ind = middle;
			length--;
		}
		
		return newHead;
		
	}
	
	public static int[] nextPermutation(int[] a){
		if(a == null || a.length <= 1) return a; 
		//find the largest k where a[k] < a[k+1]
		int k  = -1;
		for(int i = 0 ; i < a.length-1 ; i++)
			if(a[i] < a[i+1]) k = i;
		
		if(k == -1) {
			Arrays.sort(a);
			return a;
		}
		//find the largest j where a[j] > a[k]
		int j = -1;
		for(int i = 0 ; i < a.length ; i++)
			if(a[i] > a[k]) j = i;
		
		//swap a[j] and a[k];
		a[j] ^= a[k];
		a[k] ^= a[j];
		a[j] ^= a[k];
		//reverse a[k+1] to the end
		LinkedList<Integer> stack = new LinkedList<Integer>();
		for(int i = k+1 ; i < a.length ; i++)
			stack.add(a[i]);
		for(int i = k+1 ; i < a.length ; i++)
			a[i] = stack.pollLast();
		
		return a;
	}
	
	public static List<String> generateParentheses(int n){
		if(n < 0) return null;
		
		List<String> res = new ArrayList<String>();
		if(n == 1) { 
			res.add("()");
			return res;
		}
		
		List<String> temp = generateParentheses(n-1);
		for(String sb : temp){
			res.add(sb+"()");
			if(!res.get(res.size()-1).equals("()"+sb)) res.add("()"+sb);
			
			res.add("(" + sb +")");
		}
		return res;
	}
	
	/**
	 * p[i] & p[i+1] is the dimension of matrix i
	 * 
	 * m[i][j] is the minimum cost from matrix i to matrix j
	 * s[i][j] is the divide position from matrix i to matrix j
	 * s[i][j] = k where i..k-1, k...j
	 * @param p
	 */
	public static void matrixChainMultiplication(int[] p){
		if(p == null) return;
		
		int matrixNum = p.length - 1;
		int[][] m = new int[matrixNum][matrixNum];
		for(int i = 0 ; i < matrixNum ; i++)
			Arrays.fill(m[i], Integer.MAX_VALUE);
		int[][] s = new int[matrixNum][matrixNum];
		for(int i = 0 ; i < matrixNum ; i++) m[i][i] = 0;
		for(int i = 0 ; i < matrixNum-1 ; i++) {
			m[i][i+1] = p[i] * p[i+1] *p[i+2];
			s[i][i+1] = i+1;
		}
		
		for(int len = 3 ; len <= matrixNum ; len++){
			for(int start = 0 ; start <= matrixNum-len ; start++){
				int end = start + len - 1;
				for(int k = start+1 ; k <= end ; k++){//for all possible divide position
					int cost = m[start][k-1] + m[k][end] + p[start] * p[k] * p[end+1];
					if(cost < m[start][end]){
						m[start][end] = cost;
						s[start][end] = k;
					}
				}
			}
		}
		System.out.println("The minimum cost is "+m[0][matrixNum-1]);
		printRes(s, 0, s.length-1);
	}

	public static void printRes(int[][] s, int start, int end){
		if(start == end) {
			System.out.print("A"+start);
			return;
		}
		System.out.print("(");
		printRes(s, start, s[start][end]-1);
		printRes(s, s[start][end], end);
		System.out.print(")");
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode head = new ListNode(1);
		ListNode pointer = head;
		for(int i = 2 ; i < 6 ; i++){
			pointer.next = new ListNode(i);
			pointer = pointer.next;
		}
		//System.out.println(checkValid(head, 5));
		//ListNode newHead = swapNodesInPairs(head);
		
		ListNode newHead = reverseNodesInKGroup(head,3);
		int[] a = new int[]{1,4,3,2,5};
		nextPermutation(a);
		List<String> list = generateParentheses(3);
		matrixChainMultiplication(new int[]{2,1,3,4,5});
		System.out.println();
	}

}

class ListNode<T>{
	T val;
	ListNode<T> next;
	
	public ListNode(T val){
		this.val = val;
		this.next = null;
	}
}